/* Program impelementation of a single linked list.. */
/* Program by -- Akanksha (2010008) */




#include<stdio.h>
#include<stdlib.h>


//define NULL 0 


struct node
 {
   int data;
   struct node *next;
 }*head;                // head is a GLOBAL POINTER which addresses to the first node in the linked list.....

// ADD A NEW NODE AT BEGINNING 

void addbeg( int num )
   {
        

        struct node *temp;
        temp=(struct node *)malloc(sizeof(struct node));
        temp->data=num;

      
        if ( head== NULL)
         {
          head=temp;
          head->next=NULL;
         }

        else
         {
          temp->next=head;
          head=temp;
         }
   }


//THIS FUNCTION ADDS A NODE AT THE LAST OF LINKED LIST 

void append( int num)
 {
     struct node *temp,*r;
     

       temp= (struct node *)malloc(sizeof(struct node));
       temp->data=num;
       r=(struct node *)head;

      if (head == NULL) 
       {
    	 head=temp;
         head->next =NULL;
       }
      else
       {        

           while( r->next != NULL)
       		r=r->next;
            r->next =temp;
       		r=temp;
       		r->next=NULL;
     }
  }

 //  ADD A NEW NODE AFTER A SPECIFIED NO OF NODES

void addafter(int num, int loc)
  {
     int i;
     struct node *temp,*t,*r;
     r=head;       
    if(loc > count()+1 || loc <= 0)
   {
         printf("Insertion is not possible..!\nThe Linked list is still : \n");
            return;
   }
        if (loc == 1) // if the list is empty, add at the beg..
         {
           addbeg(num);
	   printf("The number '%d' is inserted in the list at the first position..\n",num); 
           return;
         }
      else
 {
       for(i=1;i<loc;i++)
          {
             t=r;   //t will be holding previous value
             r=r->next;
          }
         temp=(struct node *)malloc(sizeof(struct node));
         temp->data=num;
         t->next=temp;
         t=temp;
         t->next=r;
         printf("The number '%d' is inserted in the list at the position : '%d'..\n",num,loc);
         return;
       }
}

/* THIS FUNCTION DISPLAYS THE CONTENTS OF THE LINKED LIST */

void display(struct node *r)
  {
      r=head;
      if(r==NULL)
     {
       printf("There is no element in the list..!\n");
       return;
     }
       // traverse the entire linked list
       while(r!=NULL)
    {
      printf(" -> %d ",r->data);
      r=r->next;
    }
     printf(" ");
  }


//THIS FUNCTION COUNTS THE NUMBER OF ELEMENTS IN THE LIST


int count()
 {
   struct node *n;
   int c=0;
   n=head;
    while(n!=NULL)
   {
     n=n->next;
     c++;
   }
  return(c);
 }





 //THIS FUNCTION DELETES A NODE GIVEN THE VALUE OF THE NODE

void delete(int num)
 {   
     
     struct node *temp, *m;
     temp=head;
      while(temp!=NULL)
      {
       if(temp->data==num)
       {
           if(temp==head)
           {
              head=temp->next;
              free(temp);
              return ;
           }
           else
         {
           m->next=temp->next;
           free(temp);
	   printf("The number '%d' is deleted from the list..\n",num);
           return ;
         }
      }else
        {
           m=temp;
          temp= temp->next;
        }

}   
    printf("Element %d not found..!\nLinked list is still:\n", num);
}

/*THIS FUNCTION DELETES A NODE GIVEN THE LOCATION OF THE NODE*/

void deletenode(int loc)
{
	int i;
	struct node *temp1, *oldtemp;
	
	temp1=(struct node *)malloc(sizeof(struct node));
	temp1 = head;

	oldtemp=(struct node *)malloc(sizeof(struct node));
	oldtemp=temp1;

	if(loc > count()+1 || loc <= 0)
   		{	
			printf("Index %d not found..!\nLinked list is still: \n", loc);
        		return;
		}
	else
	  {
	
	      for(i=1; i<loc ; i++)
	        {

			oldtemp=temp1;
			temp1 = temp1->next;
	  
	  	}

	      oldtemp->next = temp1->next;
	      free(temp1);
	      printf("The number is deleted which was at the position '%d' from the list..\n",loc);
	      return ;
 	  }	

	

}






//THIS FUNCTION REVERSES A LINKED LIST


void reverse(struct node *q)
{
   struct node *m, *n,*l,*s;
   m=q;
   n=NULL;
  while(m!=NULL)
 {
   s=n;
   n=m;
  m=m->next;
  n->next=s;
 }
   head=n;
}

//THIS FUNCTION SORTS A LINKED LIST

void sort()
{
	struct node *temp1, *temp2;
	temp1=(struct node *)malloc(sizeof(struct node));
 	temp2=(struct node *)malloc(sizeof(struct node));

	int temp=0;

	for(temp1=head; temp1!=NULL; temp1= temp1->next)
	   {

		for(temp2=temp1->next; temp2!=NULL;temp2=temp2->next)
		  {

			if(temp1->data > temp2->data)
			  {

				temp=temp1->data;
				temp1->data = temp2->data;
				temp2->data = temp;

			   }
		  }

	  }

   return ;

}


void main()
 {
   int i;
   head=NULL;
   
 while(1)
 {
    printf("\n\n\n*********************************Menu****************************************\n\n");
    printf("1.Insert a number at the begining.. \n");
    printf("2.Insert a number at the last.. \n");
    printf("3.Insert a number at a particular location in list.. \n");
    printf("4.Display the element of the list.. \n");
    printf("5.Print the number of elements in the list..  \n");
    printf("6.Delete an element from the list.. \n");
    printf("7.Delete an element from the specified number of node from the list..\n");
    printf("8.Reverse the elements of the list.. \n");
    printf("9.Sort the list..\n");
    printf("10.Exit.. \n");
    printf("\nPlease, enter your choice.. : ");

    scanf("%d",&i);

      switch(i)
    {
         case 1:  {
        		int num;
        		printf("Enter the number: ");
        		scanf("%d",&num);
        		addbeg(num);
			printf("The number '%d' is inserted in the list..\n",num);
			display(head);
        		break;
      		  }
          case 2:
       		  {
         		int num;
         		printf("Enter the number: ");
         		scanf("%d",&num);
         		append(num);
			printf("The number '%d' is inserted at the last in the list..\n",num);
			display(head);
         		break;
       		  }

         case 3:
     		  {
      			int num, loc,k;
      			printf("Enter the number: ");
      			scanf("%d",&num);
      			printf("Enter the location number: ");
      			scanf("%d",&loc);
      			addafter(num,loc);
     			display(head);
			break;
    		  } 
         case 4:
                  {
         		struct node *n;
         		printf("The elements in the list are: ");
         		display(n);
         		break;
      		  }

      case 5:
                  {
      			struct node *n;
      			printf("Total no. of elements in the list : %d\n",count());
      			break;
   		  } 
      case 6:
    		{
            		int    num;
      			printf("Enter a number from the list: ");
      			scanf("%d",&num);
      			delete(num);
			display(head);
     			break;
    		}

    case 7:
		{
			int nodenum;
			printf("Enter the number of node which you want to delete : ");
			scanf("%d",&nodenum);
			deletenode(nodenum);
			display(head);
			break;
		}
	
     case 8:
    		{
      			reverse(head);
        		display(head);
        		break;
    		}

    case 9:

	    {

			sort();
			display(head);

			break;

	    }
  case 10:
 		{
  			exit(0);
 		}

	default: printf("Enter a correct choice..!!!\n");
			break;
    }
 }
}

